nums=[2,7,9,3,1]
def rob(nums):
    nums_len=len(nums)
    dp=[0 for _ in range(nums_len+1)]
    dp[0]=0
    dp[1]=nums[0]
    for i in range(2,nums_len+1):
        dp[i]=max(dp[i-1],dp[i-2]+nums[i-1])
    print(dp[nums_len])
def rob_1(nums):
    nums_len=len(nums)
    dp=[0 for _ in range(3)]
    dp[0]=0
    dp[1]=nums[0]
    for i in range(2,nums_len+1):
        dp[2]=max(dp[1],dp[0]+nums[i-1])
        dp[0]=dp[1]
        dp[1]=dp[2]
    print(dp[2])


print(rob_1(nums))